package com.leetcode;

import java.util.Arrays;

public class SuccessfulPairsOfSpellsAndPotions_2300 {

    /**
     * 暴力解法：超时
     * @param spells
     * @param potions
     * @param success
     * @return
     */
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int[] res = new int[spells.length];
        for (int i = 0; i < spells.length; i++) {
            for (int j = 0; j < potions.length; j++) {
                long sum = (long)spells[i] * (long)potions[j];
                if (sum >= success) {
                    res[i] += 1;
                }
            }
        }
        return res;
    }

    /**
     * 二分法，前提：数组有序,通过
     * @param spells
     * @param potions
     * @param success
     * @return
     */
    public int[] successfulPairs1(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int[] res = new int[spells.length];
        for (int i = 0; i < spells.length; i++) {
           int left = 0;
           int right = potions.length - 1;
           int lastPos = right;
           while (left <= right && left >= 0 && right < potions.length) {
               int mid = (left + right) / 2;
               long tmp = (long)spells[i] * (long) potions[mid];
/*               if (tmp == success) {
                   res[i] = potions.length - mid;
                   break;
               } else*/
               if (tmp >= success) {
                   lastPos = mid;
                   right = mid - 1;
               } else {
                   left = mid + 1;
               }
           }
           if (res[i] == 0 && (long)spells[i] * (long)potions[lastPos] >= success) {
               res[i] = potions.length - lastPos;
           }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] spells = {40,11,24,28,40,22,26,38,28,10,31,16,10,37,13,21,9,22,21,18,34,2,40,40,6,16,9,14,14,15,37,15,32,4,27,20,24,12,26,39,32,39,20,19,22,33,2,22,9,18,12,5};
        int[] potions = {31,40,29,19,27,16,25,8,33,25,36,21,7,27,40,24,18,26,32,25,22,21,38,22,37,34,15,36,21,22,37,14,31,20,36,27,28,32,21,26,33,37,27,39,19,36,20,23,25,39,40};
        long success = 600;
        SuccessfulPairsOfSpellsAndPotions_2300 tmp = new SuccessfulPairsOfSpellsAndPotions_2300();
        int[] res = tmp.successfulPairs1(spells,potions,success);
        System.out.println(res);
    }
}
